package cmlabs.numbertheoryutils;

import cmlabs.moduloariphmetics.PrimeField;
import cmlabs.moduloariphmetics.UsualField;

import java.math.BigInteger;
import java.util.ArrayList;
import java.util.List;

/**
 * Created by IntelliJ IDEA.
 * User: jte
 * Date: 14.4.11
 * Time: 22.37
 * To change this template use File | Settings | File Templates.
 */

public class Functions {
    public static int bisect(int a){
        return a >> 1;
    }

    public static int reserve(int a){
        return a << 1;
    }

    public static int mod(int a, int b){
        int ret = a % b;
        ret  = (ret + b ) % b;
        return ret;
    }

    public static int reverseElement(int a, int m){
        if (BigInteger.valueOf(m).isProbablePrime(20)){
            return new PrimeField(m).reverseElement(a);
        }
        else {
            return new UsualField(m).reverseElement(a);
        }
    }

    public static int phi(int a){
        Integer[] primes = getPrimes(a);
        int result = a;
        for (int i = 0; i < primes.length && pow(primes[i], 2) <= a; ++i){
            if (a % primes[i] == 0){
                while (a % primes[i] == 0){
                    a /= primes[i];
                }
                result -= result / primes[i];
            }
        }
        if (a > 1){
                result -= result / a;
        }
        return result;

    }

    public static int pow(int b, int n){
        long result  = 1;
        long a = b;
        while (n != 0){
            if ((n & 1) == 1){
                result *= a;
            }
            a *= a;
            n >>= 1;
        }
        return (int)result;
    }

    public static long powMod(long a, long n, long modulo) {
        if (a > (long) 1e9) {
            return BigInteger.valueOf(a).modPow(BigInteger.valueOf(n), BigInteger.valueOf(modulo)).longValue();
        }
        long result = 1;
        while (n != 0) {
            if ((n & 1) == 1) {
                result = (result * a) % modulo;
            }
            a = (a * a) % modulo;
            n >>= 1;
        }
        return result;
    }

    public static int gcd(int a, int b){
        return b != 0 ? gcd(b, a % b) : a;
    }

    public static long gcd(long a, long b){
        return b != 0 ? gcd(b, a % b) : a;
    }

    public static boolean areCoprime(int ...a){
        if (a.length == 0){
            throw new IllegalArgumentException();
        }
        if (a.length == 1){
            return true;
        }
        boolean ret = true;
        for (int i  = 0; i < a.length; ++i){
            for (int j = i + 1; j < a.length; ++j){
                ret &= gcd(a[i], a[j]) == 1;
            }
        }
        return ret;
    }

    public static Integer[] getPrimes(int N) {
        if (N > 1e8 || N < 2)
            throw new IllegalArgumentException("Out of memory");
        boolean[] sieve = new boolean[N + 1];
        List<Integer> primes = new ArrayList<Integer>();
        int limit = (int) Math.sqrt(N + .0);

        for (int i = 2; i <= limit; ++i) {
            if (!sieve[i]) {
                for (int j = i * i; j <= N; j += i) {
                    sieve[j] = true;
                }
                primes.add(i);
            }
        }
        for (int i = limit + 1; i <= N; ++i) {
            if (!sieve[i]) {
                primes.add(i);
            }
        }
        return (Integer[]) primes.toArray();
    }
}
